package cn.fansunion.leecode.array;

/**
 * 删除一个元素使数组严格递增。
 *  给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。
 * 
 * 数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-16
 */
public class RemoveOneElementToMakeTheArrayStrictlyIncreasing {

    /*    输入：nums = [1,2,10,5,7]
        输出：true
        解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
        [1,2,5,7] 是严格递增的，所以返回 true 。
        示例 2：
    
        输入：nums = [2,3,1,2]
        输出：false
        解释：
        [3,1,2] 是删除下标 0 处元素后得到的结果。
        [2,1,2] 是删除下标 1 处元素后得到的结果。
        [2,3,2] 是删除下标 2 处元素后得到的结果。
        [2,3,1] 是删除下标 3 处元素后得到的结果。
        没有任何结果数组是严格递增的，所以返回 false 。*/
    
    /**
     * 看了网友解题思路，关键点：怎样删除单个元素。在一次遍历的复杂度的追求下，自己之前的各种错误写法，就是没能“正确跳过”需要被删除的元素，实际分了好几种情况
     * 题目难度：暴力破解（穷举），很简单；O(N)复杂度，有难度了 TODO
     * https://leetcode-cn.com/problems/remove-one-element-to-make-the-array-strictly-increasing/solution/tan-xin-by-hu-li-hu-wai-1zni/
     * @param nums
     * @return
     */
    public boolean canBeIncreasing(int[] nums) {
        return false;
        
    }
    
    /**
     * 一次遍历。统计不严格递增的次数，超过2次，就返回false；遍历完成，返回true<br/>
     * 在canBeIncreasingError方法的基础上，调整下逻辑（简化逻辑，不用维护ignoreTimes，不用维护prev）<br/>
     * 换种思路：通常来说，简单题，代码就不应该很复杂<br/>
     * 然后，还是不对啊，哪里理解错了
     * 6 1 2 3 4 5 
     * 1 2 6 4 5 7
     * 1 2 4 5 7 6 
     * @param nums
     * @return
     */
    public boolean canBeIncreasingError3(int[] nums) {
        // 参数检查
        if (nums == null) {
            return false;
        }
        if (nums.length <= 2) {
            return true;
        }
        int notIncreasingTimes=0;
        int prev=nums[0];
        for(int index=1;index<nums.length;index++) {
            final boolean notStrictIncreacing = notStrictIncreacing(nums, prev, index);
            if(notStrictIncreacing) {
                notIncreasingTimes++;
            }
            if(notIncreasingTimes>1) {
                return false;
            }
            prev=nums[index];
        }
        return true;
    }
    
    private boolean notStrictIncreacing(int[] nums, int prev, int curIndex) {
        int cur=nums[curIndex];
        //遇到不严格递增的
        boolean curGtAfter=false;
        if(curIndex<nums.length-1 && cur>= nums[curIndex+1]) {
            curGtAfter=true;
        }
        final boolean curLtPrev = cur<=prev;
        final boolean notStrictIncreacing = curLtPrev || curGtAfter;
        return notStrictIncreacing;
    }
    
    /**
     * 一次遍历。遇到不严格递增的，忽略1次。遇到第2次，就返回false<br/>
     * 思路有误：非严格递增，可能是当前数导致的，也可能是它左右2边的数导致的。用例特殊，测试不全，没能自测发现。
     * 6 1 2 3 4 5 
     * 1 2 6 4 5 7
     * 1 2 4 5 7 6 
     * @param nums
     * @return
     */
    public boolean canBeIncreasingError(int[] nums) {
        // 参数检查
        if (nums == null) {
            return false;
        }
        if (nums.length <= 2) {
            return true;
        }
        int ignoreTimes=0;
        int prev=nums[0];
        for(int index=1;index<nums.length;index++) {
            int cur=nums[index];
            //遇到不严格递增的，最多只忽略一次；忽略情况，不修改prev
            boolean curGtAfter=false;
            if(index<nums.length-1 && cur>= nums[index+1]) {
                curGtAfter=true;
            }
            final boolean curLtPrev = cur<=prev;
            final boolean notStrictIncreacing = curLtPrev || curGtAfter;
            if(notStrictIncreacing) {
                ignoreTimes++;
                if(ignoreTimes>1) {
                   return false; 
                }
                //第1个不符合的，如果在第1个，需要特殊处理，维护prev
                if(index==1) {
                    prev=cur;
                }
            }else {
                prev=cur;
            }
        }
        return true;
    }
    
    /**
     * 一次遍历。遇到不严格递增的，忽略1次。遇到第2次，就返回false
     * error:只和prev比较了，没考虑到“严格递增”的所有情况
     * @param nums
     * @return
     */
    public boolean canBeIncreasingError2(int[] nums) {
        // 参数检查
        if (nums == null) {
            return false;
        }
        if (nums.length <= 2) {
            return true;
        }
        int ignoreTimes=0;
        int prev=nums[0];
        for(int index=1;index<nums.length;index++) {
            int cur=nums[index];
            //遇到不严格递增的，最多只忽略一次；忽略情况，不修改prev
            if(cur<=prev ) {
                ignoreTimes++;
                if(ignoreTimes>1) {
                   return false; 
                }
            }else {
                prev=cur;
            }
        }
        return true;

    }

    /**
     * 暴力破解法：不删除元素或只删除一个元素，找出所有情况；只要有1种满足数组严格递增 ，那么返回 true ，否则返回 false
     * 问题：数组特别大时，耗时太长
     * 
     * @param nums
     * @return
     */
    public boolean canBeIncreasingStupid(int[] nums) {
        // 参数检查
        if (nums == null) {
            return false;
        }
        if (nums.length <= 2) {
            return true;
        }
        boolean increasing = increasing(nums);
        if (increasing) {
            return true;
        }
        for (int index = 0; index < nums.length; index++) {
            int[] newNums = newNumsExceptOne(nums, index);
            increasing = increasing(newNums);
            if (increasing) {
                return true;
            }
        }
        return false;

    }

    public int[] newNumsExceptOne(int[] nums, int index) {
        int[] newNumsExceptOne = new int[nums.length - 1];
        for (int i = 0; i < nums.length; i++) {
            if (i < index) {
                newNumsExceptOne[i] = nums[i];
            } else if (i > index) {
                newNumsExceptOne[i - 1] = nums[i];
            } else if (i == index) {
                //啥也不做，忽略即可
            }
        }
        return newNumsExceptOne;
    }

    public boolean increasing(int[] nums) {
        // 额外判断，保证本方法的严谨性
        if (nums.length == 1) {
            return true;
        }
        //维护前一个值，默认第0个
        int prev=nums[0];
        for(int index=1;index<nums.length;index++) {
            int cur=nums[index];
            if(cur<=prev) {
                return false;
            }else {
                prev=cur;
            }
        }
        return true;
    }
    
  
}
